package me.chan.search;

/**
 * Created by JanGin on 2017/9/27.
 */
public class BinarySearchTree<Key extends Comparable<Key>, Value> {

    private class Node {
        private Key key;                // the key of the node
        private Value value;            // the value of the node
        private Node left;              // left sub node
        private Node right;             // rght sub node
        private int num;                  // the sub nodes of this node

        public Node(Key key, Value value, int N) {
            this.key = key;
            this.value = value;
            this.num = N;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    ", left=" + left +
                    ", right=" + right +
                    ", N=" + num +
                    '}';
        }
    }


    private Node root;      // the root of BST

    public int size() {
        return size(root);
    }

    private int size(Node node) {
        if (null == node) return 0;
        return node.num;
    }

    public Value get(Key key) {
        return get(root, key);
    }

    public void put(Key key, Value value) {
        //upate the root node
        root = put(root, key, value);
    }

    public void delete(Key key) {
        root = delete(root, key);
    }

    public void deleteMax() {
        root = deleteMax(root);
    }

    public void deleteMin() {
        root = deleteMin(root);
    }

    public Key min() {
        return min(root).key;
    }

    public Key max() {
        return max(root).key;
    }


    //向下取整
    public Key floor(Key key) {
        Node node = floor(root, key);
        if (null == node)
            return null;

        return node.key;
    }

    //向上取整
    public Key ceiling(Key key) {
        Node node = ceiling(root, key);
        if (null == node)
            return null;

        return node.key;
    }

    public Key select(int k) {

        return select(root, k).key;
    }

    public int rank(Key key) {
        return rank(root, key);
    }

    private Node select(Node node, int k) {
        if (null == node) return null;
        int n = size(node.left);
        if (n > k) {
            return select(node.left, k);
        } else if (n < k) {
            return select(node.right, k - n - 1);
        } else {

            return node;
        }
    }

    private int rank(Node node, Key key) {
        if (null == node) return 0;
        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            return rank(node.left, key);
        } else if (cmp > 0) {
            return size(node.left) + rank(node.right, key) + 1;
        } else {
            return size(node.left);
        }
    }

    private Node ceiling(Node node, Key key) {
        if (null == node) return null;

        int cmp = key.compareTo(node.key);
        if (cmp == 0) return node;
        if (cmp > 0) {
            return ceiling(node.right, key);
        }
        Node t = ceiling(node.left, key);
        if (t != null) {
            return t;
        } else {
            return node;
        }
    }

    private Node floor(Node node, Key key) {
        if (null == node) return null;

        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            return floor(node.left, key);
        } else if (cmp == 0) {
            return node;
        }
        Node t = floor(node.right, key);
        if (t != null) {
            return t;
        } else {
            return node;
        }

    }

    private Node min(Node node) {
        if (null == node.left) return node;
        return min(node.left);
    }

    private Node max(Node node) {
        if (null == node.right) return node;
        return max(node.right);
    }

    private Value get (Node node, Key key) {
        if (null == node) return null;

        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            return get(node.left, key);
        } else if (cmp > 0) {
            return get(node.right, key);
        } else
            return node.value;
    }

    private Node put(Node root, Key key, Value value) {
        if (null == root) {
            return new Node(key, value, 1);
        }
        int cmp = key.compareTo(root.key);
        if (cmp < 0) {
            root.left = put(root.left, key, value);
        } else if (cmp > 0) {
            root.right = put(root.right, key, value);
        } else {
            root.value = value;
        }
        root.num = size(root.left) + size(root.right) + 1;
        return root;
    }

    private Node delete(Node root, Key key) {
        if (null == root)
            return null;

        int cmp = key.compareTo(root.key);
        if (cmp < 0)
            root.left = delete(root.left, key);
        else if (cmp > 0)
            root.right = delete(root.right, key);
        else {
            if (null == root.left)
                return root.right;
            if (null == root.right)
                return root.left;

            Node node = root;
            root = min(node.right);
            root.left = node.left;
            root.right = deleteMin(node.right);
        }
        root.num = size(root.left) + size(root.right) + 1;
        return root;
    }

    // always return the root of the BST
    private Node deleteMax(Node root) {
        if (null == root.right)
            return root.left;

        root.right = deleteMax(root.right);
        root.num = size(root.left) + size(root.right) + 1;
        return root;
    }

    private Node deleteMin(Node root) {
        if (null == root.left)
            return root.right;

        root.left = deleteMin(root.left);
        root.num = size(root.left) + size(root.right) + 1;
        return root;
    }



    public static void main(String[] args) {
        BinarySearchTree<String, Integer> bst = new BinarySearchTree<>();
        bst.put("S", 0);
        bst.put("E", 1);
        bst.put("A", 2);
        bst.put("R", 3);
        bst.put("C", 4);
        bst.put("H", 5);
        bst.put("X", 7);
        bst.put("M", 9);
        bst.put("P", 10);
        bst.put("L", 11);

        /**********************************************************************/
        /**                                            S                     **/
        /**                   E                                  X           **/
        /**           A                          R                           **/
        /**               C        H                                         **/
        /**                              M                                   **/
        /**                           L      P                               **/
        /**           0   1   2    3  4  5   6   7     8         9                                                        **/
        /**********************************************************************/
        System.out.println(bst.get("H"));       //5
        System.out.println(bst.max());          //X
        System.out.println(bst.min());          //A
        System.out.println(bst.floor("F"));     //E
        System.out.println(bst.ceiling("B"));   //C
        System.out.println(bst.select(3));      //H
        System.out.println(bst.rank("P"));      //6
        System.out.println(bst.size());
        bst.deleteMax();                        //10
        System.out.println(bst.max());          //S now X before deletion
        bst.deleteMin();
        System.out.println(bst.min());          //C now A before deletion
        System.out.println(bst.size());         //8
    }
}
